import java.util.Arrays;

public class Training {

    //quick sort

    /**
     * 一次快速排序把一个元素放在正确的位置
     * 这个位置之前的数值都比它小，之后的数值都比它大
     * 通过交换，i=j的时候就是元素应该在的位置
     * 基准元素选取数组中的第一个元素
     * @param array
     * @param begin
     * @param end
     * @return
     */
    public int[] quickSort(int []array, int begin, int end) {
        if(begin > end) {
            return array;
        }

        int i = begin;
        int j = end;
        int pos = array[begin];
        while (i < j) {
            while (i < j && array[j] >= pos) {
                j --;
            }
            while (i < j && array[i] <= pos) {
                i++;
            }
            if(i < j) {
                //调换array[i], array[j]
                int temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
        }

        // 此时i = j 也就是基准元素该去的位置
        array[begin] = array[i];
        array[i] = pos;

        quickSort(array, begin, i-1);
        quickSort(array, j+1, end);
        return array;
    }

    private void quickSortResult(int array[]) {
        int []result = new Training().quickSort(array, 0, array.length-1);
        output(result);
    }


    /**
     * 递归二分查找
     * 判断中间元素与要找的元素的大小，
     * 如果中间元素比要找的值小，那在右边找
     * 如果中间元素比要找的值大，那在左边找
     * @param array
     * @param low
     * @param high
     * @param aim
     * @return
     */
    private int binSearch(int []array, int low, int high, int aim) {
        if(low > high) {
            return -1;
        }
        int middle = (low + high)/2;
        int pos = array[middle];
        if(pos == aim) {
            return middle;
        } else if(low <= high && pos > aim) {
            return binSearch(array, low, high - 1, aim);
        } else if (low <= high && pos < aim) {
            return binSearch(array, low + 1, high, aim);
        } else {
            return -1;
        }
    }

    /**
     * 二分法的非递归查找
     * @param array
     * @param aim
     * @return
     */
    private int binSearchTwo(int []array, int aim) {
        int low = 0;
        int high = array.length - 1;


        while (low <= high) {
            int middle = (low + high) / 2;
            int pos = array[middle];
            if(aim == pos) {
                return middle;
            } else if(pos < aim) {
                low = middle + 1;
            } else if(pos > aim) {
                high = middle - 1;
            }
        }
        return -1;
    }



    public static void main(String args[]) {
        int []array = new int []{1,7,3,5,2,6,9,10};
        new Training().quickSortResult(array);

        int []binArray = new int[]{1,2,3,4,5,6,7,8};
        int pos = new Training().binSearch(binArray,0, binArray.length-1, 6);
        System.out.println("pos : " + pos);
        int pos2 = new Training().binSearchTwo(binArray, 6);
        System.out.println("pos2 : " + " " + pos2);

    }

    private void output(int [] array) {
        Arrays.stream(array).forEach(item->{
            System.out.print(item + " ");
        });
        System.out.println();
    }
}
